1. Field of the Invention
The present invention applies to the field of data communications and, in particular, to a Walsh-Hadamard decoder.
2. Description of the Prior Art
In data communications, a need occasionally arises to compare a received sequence to one or more possible expected sequences. These sequences may be sequences of signal samples, modulation symbols, constellation points, bits, or any other data representation. When correlating one received sequence against a number of possible sequences, it can be helpful if the possible sequences have low auto- and cross-correlations. Various such sequences are known.
One set of sequences with desirable auto- and cross-correlation properties are the set of Walsh-Hadamard codewords of some given length. A Walsh-Hadamard decoder correlates a received codeword with all of the possible Walsh-Hadamard codewords. A transmitter selects one of these Walsh-Hadamard codewords, and transmits the codeword over a communications medium, such as radio waves, coaxial cable, optic fiber, or twisted pair. The communications medium may not be perfect because of noise or other factors, and errors can be introduced into the codeword as it is being transmitted.
A receiver receives the transmission of the codeword from the transmitter as a sequence that resembles, but is not identical to the transmitted codeword. The Walsh-Hadamard decoder determines which codeword was originally transmitted based on the received sequence. The Walsh-Hadamard decoder first correlates the received sequence with all possible Walsh-Hadamard codewords, and then chooses the codeword that has the highest correlation with the sequence as the most likely transmitted codeword.
The correlations performed by the Walsh-Hadamard decoder are computationally intensive. When implemented in hardware, Walsh-Hadamard decoders use large numbers of logic gates. Furthermore, the number of necessary logic gates increases significantly with the length of the Walsh-Hadamard code used. The large number of logic gates drives up the cost of a chip or ASIC having a Walsh-Hadamard decoder.